#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10

typedef struct TreeNode *BinTree;
typedef BinTree ElementType;

struct TreeNode
{
    int Data;
    BinTree left;
    BinTree right;
};
// 接下来我们来看看二叉树遍历中的层序遍历
// 考虑到队列先进先出的特点，我们可以利用队列的特性来建立层序遍历

/*思路如下：
      从根节点入队
      1.从队列中取出一个元素并访问
      2.若该元素所指结点的左右孩子结点非空，则将孩子入队
*/

// 我们先来构建队列的基本操作
struct QNode
{
    ElementType data[MAXSIZE];
    int rear;  // 队尾
    int front; // 队头
};
typedef struct QNode *Queue;

int IsEmpty(Queue PtrQ)
{
    if (PtrQ->rear == PtrQ->front)
        return 1;
    else
        return 0;
}
int IsFull(Queue PtrQ)
{
    if ((PtrQ->rear + 1) % MAXSIZE == PtrQ->front)
        return 1;
    else
        return 0;
}

Queue CreateQueue(void)
{
    Queue PtrQ = (Queue)malloc(sizeof(struct QNode));
    PtrQ->front = PtrQ->rear = 0;
    return PtrQ;
}

void AddQueue(Queue PtrQ, ElementType item)
{
    if (IsFull(PtrQ))
    {
        printf("队列满，加不了啦\n");
        return;
    }
    else
    {
        PtrQ->rear = (PtrQ->rear + 1) % MAXSIZE;
        PtrQ->data[PtrQ->rear] = item;
    }
}

ElementType DeleteQueue(Queue PtrQ)
{
    if (IsEmpty(PtrQ))
    {
        printf("队列为空，删不了啦");
        return NULL;
    }
    else
    {
        PtrQ->front = (PtrQ->front + 1) % MAXSIZE;
        return PtrQ->data[PtrQ->front];
    }
}

// 接下来我们来构建层序遍历的算法
void LevelOrderTraversal(BinTree BT)
{
    Queue Q;
    BinTree T;
    if (BT == NULL)
        return;        // 如果是空树就直接结束
    Q = CreateQueue(); // 创建并初始化队列Q
    AddQueue(Q, BT);

    while (!IsEmpty(Q))
    {
        T = DeleteQueue(Q);
        printf("%d ", T->Data);

        if (T->left != NULL)
            AddQueue(Q, T->left);
        if (T->right != NULL)
            AddQueue(Q, T->right);
    }
}

/* // 测试代码
BinTree CreateTree()
{
    BinTree root = (BinTree)malloc(sizeof(struct TreeNode));
    root->Data = 1;
    root->left = (BinTree)malloc(sizeof(struct TreeNode));
    root->left->Data = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (BinTree)malloc(sizeof(struct TreeNode));
    root->right->Data = 3;
    root->right->left = (BinTree)malloc(sizeof(struct TreeNode));
    root->right->left->Data = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (BinTree)malloc(sizeof(struct TreeNode));
    root->right->right->Data = 5;
    root->right->right->left = NULL;
    root->right->right->right = NULL;
    return root;
}

int main()
{
    BinTree tree = CreateTree();
    printf("层序遍历结果：");
    LevelOrderTraversal(tree);
    return 0;
} */
